package cn.michael.dev.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * Created by hufenggang on 2021/10/21.
 *
 * 快速排序
 */
public class QuickSort {

    private static final int INSERTION_SORT_THRESHOLD = 7;
    private static final Random RANDOM = new Random();

    /**
     * 数组快速排序
     *
     * @param array
     */
    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 数组区间内快速排序
     *
     * @param array 输入数组
     * @param left  划分左边界
     * @param right 划分右边界
     */
    public static void quickSort(int[] array, int left, int right) {

        // 小区间使用插入排序
        if (right - left < INSERTION_SORT_THRESHOLD) {
            insertionSort(array, left, right);
            return;
        }

        int pIndex = partition(array, left, right);
        quickSort(array, left, pIndex - 1);
        quickSort(array, pIndex + 1, right);
    }

    /**
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] nums, int left, int right) {
        int randomIndex = RANDOM.nextInt(right - left + 1) + left;
        swap(nums, left, randomIndex);

        // 基准值
        int pivot = nums[left];
        int lt = left;

        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                lt++;
                swap(nums, i, lt);
            }
        }

        swap(nums, left, lt);
        return lt;
    }

    /**
     * 交换数组
     *
     * @param nums
     * @param i
     * @param j
     */
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 对数组 nums 的子区间 [left, right] 使用插入排序
     *
     * @param nums  给定数组
     * @param left  左边界
     * @param right 右边界
     */
    private static void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = nums[i];
            int j = i;
            while (j > left && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 4, 6, 8, 3, 10, 4, 6};
        insertionSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
